package com.zdp.leetcodeMiddle;


import java.util.*;

/*
* 题目描述：
* 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/group-anagrams
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 字母异位词分组_49 {
    public static void main(String[] args) {
        字母异位词分组_49 demo = new 字母异位词分组_49();
        String[] strs = new String[]{
                "eat","tea","tan","ate","nat","bat"
        };
        List<List<String>> lists = demo.groupAnagrams(strs);
        System.out.println(lists.size());
        for(List<String> temp :lists){
            for(int i=0;i<temp.size();i++){
                System.out.print(temp.get(i)+",");
            }
            System.out.println();
        }
    }

    /*
    * 超时了
    * */
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<>();
        Set<Integer> only = new HashSet<>();
        for(int i=0;i<strs.length;i++){
            if(only.contains(Integer.valueOf(i))){
                continue;
            }
            // 处理一下
            int[] wordNums = new int[26];
            List<String> temp = new ArrayList<>();
            String t = strs[i];
            temp.add(t);
            for(int j=0;j<t.length();j++){
                wordNums[t.charAt(j)-'a']++;
            }
            // 字符串数组中有几个异位词
            int k=i+1;
            while(k<strs.length){
                if(only.contains(Integer.valueOf(k))){
                    k++;
                    continue;
                }
                boolean ff = true;
                String sk = strs[k];
                if(!sk.equals(t)){
                    // 判断是否异位词
                    int[] wordNums1 = new int[26];
                    for(int j=0;j<sk.length();j++){
                        wordNums1[sk.charAt(j)-'a']++;
                    }
                    for(int j=0;j<26;j++){
                        if(wordNums[j] != wordNums1[j]){
                            ff = false;
                            break;
                        }
                    }
                }
                // 记录一下
                if(ff){
                    temp.add(strs[k]);
                    only.add(k);
                }
                k++;
            }
            result.add(temp);
        }

        return result;
    }

    /*
    * 利用哈希表 +  异位词：单词数量相同，但位置不同，所以排序后，会一样
    * */
    public List<List<String>> groupAnagrams1(String[] strs) {
        Map<String,List<String>> result = new HashMap<>();
        for(String str : strs){
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            List<String> orDefault = result.getOrDefault(key, new ArrayList<String>());
            orDefault.add(str);
            result.put(key,orDefault);
        }
        return new ArrayList<List<String>>(result.values());
    }

}
